package leetcode.all;

public class Solution375 {
    /**
     * 动态规划：dp[i][j]表示从[i...j]中猜数字的最小成本
     * dp[i][j] = min{k + max(dp[i][k-1],dp[k+1][j]), i<=k<=j}
     */
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n+2][n+2]; //外围补两行两列，后面计算不用再判断
        //由转移方程可见，需从对角线往右上角走，默认对角线就是0相当于已经初始化了
        for (int len = 2; len <= n; len++) {
            for (int i = 1, j = len; j <= n; i++, j++) { //对角线最左上开始
                dp[i][j] = Integer.MAX_VALUE;
                for (int q = i; q <= j; q++) {//选q作为从[i...j]中猜数字的第一个选择
                    dp[i][j] = Math.min(dp[i][j],q+Math.max(dp[i][q-1],dp[q+1][j]));
                }
            }
        }
        return dp[1][n];
    }
}
